package com.chao.stucture.list;

import java.util.LinkedList;

/**
 * @author : Rookie
 * @description : 双向链表
 * @date : 2022/11/6
 */
public class DoubleLinkedList<E> {

    /**
     * 头节点
     */
    private Node<E> head;
    /**
     * 尾节点
     */
    private Node<E> tail;
    /**
     * 链表大小
     */
    private int size;

    /**
     * 节点内部类
     */
    static class Node<E> {
        /**
         * 上一节点
         */
        private Node<E> prev;
        /**
         * 下一节点
         */
        private Node<E> next;
        /**
         * 元素
         */
        private E element;

        public Node(E element) {
            this.element = element;
            this.prev = null;
            this.next = null;
        }

        public Node(E element,Node<E> prevNode,Node<E> nextNode) {
            this.element = element;
            this.next = nextNode;
            this.prev = prevNode;
        }
    }

    /**
     * 尾插法
     * @param element
     */
    public void addLast(E element) {
        //创建节点实体对象
        Node<E> newNode = new Node<>(element);
        //判断双向链表中是否有元素
        if (this.tail == null) {
            this.head = newNode;
        }else {
            newNode.prev = this.tail;
            this.tail.next = newNode;
        }
        this.tail = newNode;
        this.size ++;
    }

    /**
     * 头插法
     * @param element
     */
    public void addFirst(E element) {
        //创建节点实体对象
        Node<E> newNode = new Node<>(element);
        //判断双向链表中是否有元素
        if (this.head == null) {
            this.tail = newNode;
        }else {
            newNode.next = this.head;
            this.head.prev = newNode;
        }
        this.head = newNode;
        this.size ++;
    }

    /**
     * 插入到指定位置
     * @param position 位置
     * @param element 元素
     */
    public void add(int position, E element) {
        Node<E> newNode = new Node<>(element);
        //判断是否越界
        if(position < 0 || position >= this.size) {
            throw new RuntimeException("链表越界！");
        }
        //判断是否插入头部
        if (position == 0) {
            addFirst(element);
        } else if (position == size) {
            addLast(element);
        } else {
            Node<E> currNode = this.head;
            Node<E> preNode = null;
            int index = 0;
            // 遍历找到目标节点及前一个节点
            while (index < position) {
                preNode = currNode;
                currNode = currNode.next;
                index ++;
            }
            // 前一节点的next指向新的节点
            preNode.next = newNode;
            // 目标节点的prev指向新节点
            currNode.prev = newNode;
            // 新节点的prev指向前一节点
            newNode.prev = preNode;
            // 新节点的next指向目标节点
            newNode.next = currNode;
            this.size ++;
        }
    }

    public void display() {
        Node<E> currNode = this.head;
        StringBuilder sb = new StringBuilder();
        while (currNode != null) {
            sb.append(currNode.element);
            if (currNode.next != null) {
                sb.append("->");
            }
            currNode = currNode.next;
        }
        System.out.print(sb);
    }

    public void remove(E element) {
        int index = indexOf(element);
        if (index == -1) {
            throw new RuntimeException("链表中未查询到当前元素！");
        }
        //判断是否越界
        if(index < 0 || index >= this.size) {
            throw new RuntimeException("链表越界！");
        }

        // 如果删除的是头节点
        if (index == 0) {
            // 当前链表只有一个节点
            if (this.size == 1) {
                this.head = null;
                this.tail = null;
            } else {
                this.head = this.head.next;
                this.head.prev = null;
            }
        } else {
            Node<E> currNode = this.head;
            Node<E> preNode = null;
            int i = 0;
            // 向下遍历并记住前一个节点
            while (i < index) {
                preNode = currNode;
                currNode = currNode.next;
                i ++;
            }
            // 不是最后一个节点
            if (currNode.next != null) {
                preNode.next = currNode.next;
                currNode.next.prev = preNode;
            } else {
                preNode.next = null;
                this.tail = preNode;
            }
        }
        this.size --;
    }

    /**
     * 移除指定位置的元素
     * @param position
     */
    private void removeAt(int position) {
        E e = get(position);
        remove(e);
    }

    /**
     * 获取元素在链表中的索引
     * @param e
     * @return
     */
    private int indexOf(E e) {
        Node<E> currNode = this.head;
        int index = 0;
        while (index < size) {
            if (currNode.element.equals(e)) {
                return index;
            }
            currNode = currNode.next;
            index ++;
        }
        return -1;
    }

    /**
     * 获取指定索引处的元素
     * @param i
     * @return
     */
    public E get(int i) {
        if (i < 0 || i >= size) {
            throw new RuntimeException("链表越界！");
        }
        Node<E> currNode = this.head;
        int index = 0;
        while (index < i) {
            currNode = currNode.next;
            index ++;
        }
        return currNode.element;
    }

    public static void main(String[] args) {
        DoubleLinkedList<String> doubleLinkedList = new DoubleLinkedList<>();
        doubleLinkedList.addLast("A");
        doubleLinkedList.addFirst("B");
        doubleLinkedList.addLast("C");
        doubleLinkedList.addFirst("D");
        doubleLinkedList.addLast("E");
        doubleLinkedList.add(3,"FF");
        doubleLinkedList.remove("D");
        doubleLinkedList.remove("FF");
        doubleLinkedList.removeAt(3);
        doubleLinkedList.display();
    }
}
